package com.yinxin.wudasuanfa.huaweiod;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Random;

/**
 * @author yinxin
 * @version 1.0
 * @Description: 叠书：给定一个二维数组类似于"[[20,16],[20,21],[10,20],[9,10]]"，
 * 对于二维数组的每一个元素：第一个元素表示书的宽度，第二个元素表示书的高度，
 * 叠在上面的书比在下面的书宽度和高度都要小，求最多能叠的书的数量
 * @date 2022/5/915:37
 */
public class Exercise8 {
    public static void main(String[] args) {
        int[][] arr = {{20,16},{20,21},{10,20},{9,10},{64,45},{42,95},{80,37},{79,84},
                {51,23},{13,15},{60,69},{32,88},{53,91},{91,87},{57,30},{83,84}};//定义数组
        //先排第一个数
        for (int i = 0; i < arr.length-1; i++) {
            for (int j = 0; j < arr.length-1-i; j++) {
                if(arr[j][0]>arr[j+1][0]){
                    swapArr(arr,j,j+1);
                }
            }
        }
        int[] myArr = new int[arr.length];
        //排序(第一个数字排序，小到大)
        for (int i = 0; i < arr.length; i++) {
            myArr[i]=arr[i][1];
        }
        //System.out.println(Arrays.toString(myArr));
        long times = System.currentTimeMillis();
        LIS lis = new LIS(myArr);
        int foo1 = lis.foo();
        System.out.println("动态规划使用的时间是："+(System.currentTimeMillis()-times));
        System.out.println("结果是:"+foo1);
        times=System.currentTimeMillis();
        int foo2 = foo(myArr, myArr.length - 1);
        System.out.println("不用动态规划使用的时间是："+(System.currentTimeMillis()-times));
        System.out.println("结果是:"+foo2);
    }

    /*public static void main(String[] args){
        int[] arr = new int[31];
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(100);
        }
    }*/
// 最长递增子序列
    private static class LIS {
//    longest increasing subsequence
        int[] arr;
        HashMap<Integer,Integer> values = new HashMap<>();
        LIS(int[] arr) {
            this.arr = arr;
        }
        int foo() {
            return foo(arr, arr.length - 1);
        }
        private int foo(int[] arr, int end) {
            //先从动态规划存储的foo(arr,end)的结果中拿到存储的值，拿不到就要走逻辑计算。
            Integer value = values.get(end);
            if (value != null) {
                return value;
            }
            if (end == 0) {
                values.put(0, 1);//每次返回时存值
                return 1;
            }
            int len = 0;
            for (int i = 0; i < end; i++) {
                int temp = foo(arr, i);
                len = Math.max(len, arr[end] > arr[i] ? temp + 1 : temp);
            }
            values.put(end, len);//每次返回时存值
            return len;
        }
    }

    private static int foo(int[] arr, int end) {
        if (end == 0) {
            return 1;
        }
        /** 设计思路--
         * 设 foo(k) 对应代码中的foo(int[] arr, int end)为：
         * 以数列中第k项 (为了与java数组逻辑一致，这里的k从0开始计算) 结尾的最长递增子序列的长度
         * 则：
         * foo(0) == 1
         * foo(k) == max(
         * arr[k]>arr[0]?foo(0)+1:foo(0),
         * arr[k]>arr[1]?foo(1)+1:foo(1) ,
         * ... ,
         * arr[k]>arr[k-1]?foo(k-1)+1:foo(k-1)
         * )
         */
        int len = 0;
        for (int i = 0; i < end; i++) {
            int temp = foo(arr,i);
            len = Math.max(len,arr[end]>arr[i]?temp+1:temp);//这里的len是foo(i-1)的值
        }
        return len;
    }


    public static void swapArr(int[][] arr, int after, int before) {
        int[] tmp = arr[after];
        arr[after] = arr[before];
        arr[before] = tmp;
    }

}
